#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    ListNode* copyRandomList(ListNode* head) {
        unordered_map<ListNode*, ListNode*> hash;
        hash[nullptr] = nullptr;
        auto dup = new ListNode(-1), tail = dup;

        while (head)
        {
            if (!hash.count(head)) hash[head] = new ListNode(head->val);
            if (!hash.count(head->random)) hash[head->random] = new ListNode(head->random->val);

            tail->next = hash[head];
            tail->next->random = hash[head->random];

            tail = tail->next;
            head = head->next;
        }

        return dup->next;
    }
};

